/**
 *    Copyright (C) 2008, 2009  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef _CUBEFS_CORE_TOOLS_PACKED_MAP_H
#define _CUBEFS_CORE_TOOLS_PACKED_MAP_H

#include <cubefs/core/tools/buffer.hpp>
#include <cubefs/core/tools/types/typehash.hpp>
#include <cubefs/core/tools/packed_map_intrnl.hpp>

#include <cubefs/core/tools/reflection.hpp>

#include <iostream>
#include <typeinfo>

namespace cubefs        {
namespace tools         {

using cubefs::api::MetadataList;
//using cubefs::tools::FieldFactory;

template   <typename KeyType,
            typename ValueType,
            typename Constants,
            long Indexes = 1,
            typename IndexKeyType = KeyType,
            typename Accumulator = Tracker<IndexKeyType>,
            typename CmpLT = CompareLT<IndexKeyType>,
            typename CmpLE = CompareLE<IndexKeyType>,
            typename CmpEQ = CompareEQ<IndexKeyType> >
class PackedMap: public Buffer<Constants::BLOCK_SIZE> {
public:
    typedef KeyType                             Key;
    typedef ValueType                           Value;
    typedef IndexKeyType                        IndexKey;

    
    typedef PackedMap<
                KeyType,
                ValueType,
                Constants,
                Indexes,
                IndexKey,
                Accumulator,
                CmpLT,
                CmpLE,
                CmpEQ
    >                                                                           Me;

    static const long INDEXES   = Indexes;

    static const Int kHashCode  = ListHash<
                        typename TypeListTool<
                            Key,
                            ValueType,
                            HashCode<Constants::BLOCK_SIZE>,
                            HashCode<Indexes>,
                            IndexKey
                        >::List
    >::Value;


private:
    typedef Buffer<Constants::BLOCK_SIZE> base;

    static const Int children       = Constants::CACHE_LINE_WIDTH / (sizeof(IndexKey) * Indexes) * 4;

    static const Int size_offset    = 0;                //all offsets are in bytes
    static const Int index_offset   = sizeof(Int);

    static const size_t value_size = ValueTraits<ValueType>::Size;

    static Int      index_size_;
    static Int      data_offset_;
    static Int      max_size_;

    static bool     initialized;

public:

    PackedMap(): base () {
        initialized = true;
    }

    MetadataList GetFields(Long &abi_ptr) const {
        MetadataList list;

        FieldFactory<Int>::create(list, size(), "SIZE", abi_ptr);
        FieldFactory<IndexKeyType>::create(list, index(0), "INDEX", index_size(), abi_ptr);

        for (Int c = 0; c < max_size(); c++) {
            MetadataList dataList;
            FieldFactory<Key>::create(dataList, key(c), "KEYS", Indexes, abi_ptr);

            if (value_size > 0) {
                FieldFactory<Value>::create(dataList, data(c), "DATA", abi_ptr);
            }

            list.push_back(new MetadataGroupImpl("ITEM", dataList));
        }

        return list;
    }

    static int kind() {
        return Constants::KIND;
    }

    static Int block_size() {
        return Constants::BLOCK_SIZE;
    }

    const Int &size() const {
        return *(Int*)(base::ptr() + size_offset);
    }

    Int &size() {
        return *(Int*)(base::ptr() + size_offset);
    }

    static Int index_size() {
        return index_size_;
    }

    static Int max_size() {
        return max_size_;
    }

    const IndexKey &index(Int n) const {
        return index(0, n);
    }

    IndexKey &index(Int n) {
        return index(0, n);
    }

    const IndexKey &index(Int i, Int n) const {
        Int idx = index_offset + n * sizeof(IndexKey)*Indexes + sizeof(IndexKey) * i;
        return *(IndexKey*)(base::ptr() + idx);
    }

    IndexKey &index(Int i, Int n) {
        Int idx = index_offset + n * sizeof(IndexKey)*Indexes + sizeof(IndexKey) * i;
        return *(IndexKey*)(base::ptr() + idx);
    }

    const KeyType &key(Int n) const {
        return key(0, n);
    }

    KeyType &key(Int n) {
        return key(0, n);
    }

    const KeyType &key(Int i, Int n) const {
        Int idx = data_offset_ + n * (sizeof(KeyType)*Indexes + value_size) + sizeof(KeyType) * i;
        return *(KeyType*)(base::ptr() + idx);
    }

    KeyType &key(Int i, Int n) {
        Int idx = data_offset_ + n * (sizeof(KeyType)*Indexes + value_size) + sizeof(KeyType) * i;
        return *(KeyType*)(base::ptr() + idx);
    }


    const KeyType* keys(Int n) const {
        Int idx = data_offset_ + n * (sizeof(KeyType)*Indexes + value_size);
        return (KeyType*)(base::ptr()  + idx);
    }

    KeyType* keys(Int n) {
        Int idx = data_offset_ + n * (sizeof(KeyType)*Indexes + value_size);
        return (KeyType*)(base::ptr()  + idx);
    }
    
    const ValueType &data(Int n) const {
        Int idx = data_offset_ + n * (sizeof(KeyType)*Indexes + value_size) + sizeof(KeyType)*Indexes;
        return *(ValueType*)(base::ptr() + idx);
    }

    ValueType &data(Int n) {
        Int idx = data_offset_ + n * (sizeof(KeyType)*Indexes + value_size) + sizeof(KeyType)*Indexes;
        return *(ValueType*)(base::ptr() + idx);
    }

    Int Add(KeyType k, const ValueType &value) {
        set(size(), k, value);
        size()++;
        return size();
    }

    Int Add(KeyType k) {
        key(size()) = k;
        size()++;
        return size();
    }

    void set(Int idx, KeyType k, const ValueType &value) {
        set(0, idx, k, value);
    }

    void set(Int i, Int idx, KeyType k, const ValueType &value) {
        set_key(i, idx, k);
        set_data(i, idx, value);
    }

    IndexKey max_key() const {
        return max_key(0);
    }

    IndexKey max_key(Int i) const {
        return index(i, 0);
    }

    KeyType min_key() const {
        return min_key(0);
    }

    KeyType min_key(Int i) const {
        return key(i, 0);
    }

    void Reindex() {
        for (Int c = 0; c < Indexes; c++) {
            Reindex(c);
        }
    }

    void Reindex(Int index_num) {
        Int _size = size();
        if (_size > 0) {
            Int isize = get_index_size(_size);
            Int size0 = get_parent_nodes_for(_size);
            Accumulator acc;
            Int idx;
            for (idx = 0; idx < (_size - _size % children); idx += children) {

                for (Int i = idx; i < idx + children; i++) {
                    acc(key(index_num, i));
                }

                index(index_num, isize - size0 + (idx / children)) = acc.get();
                acc.Reset();
            }

            if ((_size % children) != 0) {
                for (Int i = idx; i < _size; i++) {
                    acc(key(index_num, i));
                }

                index(index_num, isize - size0 + (idx / children)) = acc.get();
            }

            Int i_base = isize - size0;
            _size = size0;

            while (size0 > 1) {
                size0 = get_parent_nodes_for(_size);
                Accumulator acc1;

                for (idx = 0; idx < (_size - _size % children); idx += children) {
                    for (Int i = idx + i_base; i < idx + children + i_base; i++) {
                        acc1(index(index_num, i));
                    }
                    
                    index(index_num, i_base - size0 + (idx / children)) = acc1.get();
                    acc1.Reset();
                }

                if ((_size % children) != 0) {
                    for (Int i = idx + i_base; i < _size + i_base; i++) {
                        acc1(index(index_num, i));
                    }

                    index(index_num, i_base - size0 + (idx / children)) = acc1.get();
                }

                i_base -= size0;
                _size = size0;
            }
        }
    }

    template <typename IndexComparator, typename DataComparator>
    Int Find(Int index_num, KeyType k, IndexComparator &index_comparator, DataComparator &data_comparator) const {

        if (data_comparator.TestMax(k, max_key(index_num))) {
            return -1;
        }

        Int levels = get_levels_for_size(size());
        Int base = 0, start = 0;

        for (Int level = 0; level < levels; level++) {
            Int size = get_elements_on_level(level);

            for (Int idx = start; idx < size; idx++) {
                KeyType key0 = index(index_num, base + idx);
                if (index_comparator(k, key0)) {
                    start = (idx * children);
                    index_comparator.Sub(key0);
                    break;
                }
            }

            base += size;
        }

        data_comparator.Reset(index_comparator.get());

        Int _size = size();
        Int stop = (start + children) > _size ? _size : start + children;
        for (Int idx = start; idx < stop; idx++) {
            KeyType key0 = key(index_num, idx);
            if (data_comparator(k, key0)) {
                return idx;
            }
        }
        return -1;
    }

    Int FindLT(KeyType k) const {
        return FindLT(0, k);
    }

    Int FindLT(Int i, KeyType k) const {
        CmpLT lt0, lt1;
        return Find(i, k, lt0, lt1);
    }

    Int FindLTS(KeyType k, KeyType &sum) const {
        return FindLT(0, k, sum);
    }

    Int FindLTS(Int i, KeyType k, KeyType &sum) const {
        CmpLT lt0, lt1;
        Int idx = Find(i, k, lt0, lt1);
        sum += lt1.get() - (size() > 0 ? key(i, idx) : 0);
        return idx;
    }

    Int FindLE(KeyType k) const {
        return FindLE(0, k);
    }

    Int FindLE(Int i, KeyType k) const {
        CmpLE le0, le1;
        return Find(i, k, le0, le1);
    }

    Int FindLES(KeyType k, KeyType &sum) const {
        return FindLES(0, k, sum);
    }

    Int FindLES(Int i, KeyType k, KeyType &sum) const {
        CmpLE le0, le1;
        Int idx = Find(i, k, le0, le1);
        sum += le1.get() - (size() > 0 ? key(i, idx) : 0);
        return idx;
    }

    Int FindEQ(KeyType k) const {
        return FindEQ(0, k);
    }

    Int FindEQ(Int i, KeyType k) const {
        CmpLE le;
        CmpEQ eq;
        return Find(i, k, le, eq);
    }

    KeyType Prefix(Int i, Int idx, KeyType sum) const {
        return sum - key(i, idx);
    }

    void Dump(std::ostream &os) const {
        Dump(0, os);
    }

    void Dump(Int i, std::ostream &os) const {

        Int _size = size();
        os<<"------------------------------------------"<<std::endl;
        os<<"Key: "<<TypeNameFactory<KeyType>::name()<<" IndexKey: "<<TypeNameFactory<IndexKey>::name()<<std::endl;
        os<<"levels: ";
        Int nlevels = get_levels_for_size(_size);
        for (Int c = 0, count = 0; c < nlevels; c++) {
            count = get_elements_on_level(c);
            os<<count<<" ";
        }
        os<<std::endl;

        os<<"size: "<<size()<<std::endl;
        os<<"index:"<<std::endl;

        Int isize = get_index_size(_size);
        for (Int c = 0; c < isize; c++) {
            os<<c<<":"<<index(i, c)<<" ";
        }

        os<<std::endl;
        os<<"data:"<<std::endl;
        for (Int c = 0; c < _size; c++) {
            os<<c<<":"<<key(i, c)<<" ";
        }
        os<<std::endl;
    }

    void MoveData(Int dest, Int src, Int count, KeyType k, const ValueType &value) {
        Int c;
        if (src < dest) {
            --src;
            --dest;
            for(c = count; c > 0 ; c--) {
                key(dest + c) = key(src + c);
                key(src + c) = k;
                if (value_size > 0) {
                    data(dest + c) = data(src + c);
                    data(src + c)  = value;
                }
            }
        }
        else {
            for(c = 0; c < count ; c++) {
                key(dest + c) = key(src + c);
                key(src + c) = k;
                if (value_size > 0) {
                    data(dest + c) = data(src + c);
                    data(src + c)  = value;
                }
            }
        }
    }

    void MoveData(Int dest, Int src, Int count) {
        Int c;
        if (src < dest) {
            --src;
            --dest;
            for(c = count; c > 0 ; c--) {
                for (Int j = 0; j < Indexes; j++) {
                    key(j, dest + c) = key(j, src + c);
                }

                if (value_size > 0) {
                    data(dest + c) = data(src + c);
                }
            }
        }
        else {
            for(c = 0; c < count ; c++) {
                for (Int j = 0; j < Indexes; j++) {
                    key(j, dest + c) = key(j, src + c);
                }

                if (value_size > 0) {
                    data(dest + c) = data(src + c);
                }
            }
        }
    }

    void CopyData(Int from, Int count, Me &other, Int to) const {
        for(Int c = from; c < from + count ; c++) {
            for (Int j = 0; j < Indexes; j++) {
                other.key(j, to + c - from) = key(j, c);
            }

            if (value_size > 0) {
                other.data(to + c - from) = data(c);
            }
        }
    }

    void MoveData(Int dest, Int src, Int count, KeyType k) {
        MoveData(dest, src, ValueType());
    }

    //TODO: needs testing
    void Remove(Int idx, Int count) {
        const Int size0 = size();
        MoveData(idx, idx + count, size0 - idx - count);
        size() -= count;

        for (Int c = size(); c < size0; c++) {
            key(c) = 0;
        }
    }

    Int get_index_levels_count() const {
        return get_levels_for_size(size());
    }

    Int get_elements_on_level(Int level) const {
        Int _size = size();
        Int levels = get_levels_for_size(_size);

        for (Int nlevels = levels - 1; nlevels >= level; nlevels--) {
            _size = ((_size % children) == 0) ? (_size / children) : (_size / children) + 1;
        }

        return _size;
    }

    void MoveTo(PackedMap<KeyType, ValueType, Constants, Indexes, IndexKey, Accumulator, CmpLT, CmpLE, CmpEQ> &target, Int from) {
        Int count = size() - from;

        if (target.size() > 0) {
            target.MoveData(count, 0, target.size());
        }

        for (Int i = from; i < size(); i++) {
            target.set_key(i - from, key(i));
            if (value_size > 0) {
                target.set_data(i - from, data(i));
            }
        }

        Reindex();
        target.Reindex();
    }

protected:

    static Int get_index_size(Int csize) {
        if (csize == 1) {
            return 1;
        }
        else {
            Int sum = 0;
            for (Int nlevels=0; csize > 1; nlevels++) {
                csize = ((csize % children) == 0) ? (csize / children) : (csize / children) + 1;
                sum += csize;
            }
            return sum;
        }
    }

    static Int get_levels_for_size(Int csize) {
        Int nlevels;
        for (nlevels=0; csize > 1; nlevels++) {
            csize = ((csize % children) == 0) ? (csize / children) : (csize / children) + 1;
        }
        return nlevels;
    }

    static Int get_parent_nodes_for(Int n) {
        return (n % children) == 0 ? n / children : ((n / children) + 1);
    }

    static Int get_block_size(Int item_count) {
        Int key_size = sizeof(IndexKey) * Indexes;
        Int item_size = sizeof(KeyType)*Indexes + value_size;
        return get_index_size(item_count) * key_size + item_count * item_size;
    }
public:
    static bool Init();
};



template   <typename Key,
            typename Value,
            typename Constants,
            long Indexes,
            typename IndexKey,
            typename Accumulator,
            typename CmpLT,
            typename CmpLE,
            typename CmpEQ>
Int PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator, CmpLT, CmpLE, CmpEQ>::data_offset_    = 0;

template   <typename Key,
            typename Value,
            typename Constants,
            long Indexes,
            typename IndexKey,
            typename Accumulator,
            typename CmpLT,
            typename CmpLE,
            typename CmpEQ>
Int PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator, CmpLT, CmpLE, CmpEQ>::index_size_     = 0;

template   <typename Key,
            typename Value,
            typename Constants,
            long Indexes,
            typename IndexKey,
            typename Accumulator,
            typename CmpLT,
            typename CmpLE,
            typename CmpEQ>
Int PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator, CmpLT, CmpLE, CmpEQ>::max_size_       = 0;


template   <typename Key,
            typename Value,
            typename Constants,
            long Indexes,
            typename IndexKey,
            typename Accumulator,
            typename CmpLT,
            typename CmpLE,
            typename CmpEQ>
bool PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator, CmpLT, CmpLE, CmpEQ>::Init() {
    Int block_size = Constants::BLOCK_SIZE - sizeof(Int);
    Int item_size = sizeof(Key)*Indexes + value_size;
    
    Int first = 1;
    Int last  = block_size / item_size;
    while (first < last - 1) {
        Int middle = (first + last) / 2;

        Int size = get_block_size(middle);
        if (size < block_size) {
            first = middle;
        }
        else if (size > block_size) {
            last = middle;
        }
        else {
            break;
        }
    }

    if (get_block_size(last) <= block_size) {
        max_size_ = last;
    }
    else if (get_block_size((first + last) / 2) <= block_size) {
        max_size_ = (first + last) / 2;
    }
    else {
        max_size_ = first;
    }

    index_size_ = get_index_size(max_size_);

    data_offset_ = sizeof(Int) + index_size_ * sizeof(IndexKey) * Indexes;

    initialized = true;

    return true;
}

template   <typename Key,
            typename Value,
            typename Constants,
            long Indexes,
            typename IndexKey,
            typename Accumulator,
            typename CmpLT,
            typename CmpLE,
            typename CmpEQ>
bool PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator, CmpLT, CmpLE, CmpEQ>::initialized =
    PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator, CmpLT, CmpLE, CmpEQ>::Init();

template <typename Key, typename Value, typename Constants, long Indexes = 1, typename IndexKey = Key>
class PackedValueMap: public PackedMap <Key, Value, Constants, Indexes, IndexKey> {
public:
    PackedValueMap(): PackedMap<Key, Value, Constants, Indexes, IndexKey>() {}

    bool IsValueMap() {
        return PackedMap <Key, Value, Constants, Indexes, IndexKey>::get_kind() == 0;
    }
};

template <typename Key, typename Value, typename Constants, long Indexes = 1, typename IndexKey = Key>
class PackedIndexMap: public PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator<IndexKey>, CompareLTAcc<IndexKey>, CompareLEAcc<IndexKey>, CompareEQAcc<IndexKey> > {
    typedef PackedMap<Key, Value, Constants, Indexes, IndexKey, Accumulator<IndexKey>, CompareLTAcc<IndexKey>, CompareLEAcc<IndexKey>, CompareEQAcc<IndexKey> > base;
public:
    PackedIndexMap(): base() {}

    bool IsValueMap() {
        return base::get_kind() == 0;
    }
};


template <
        typename Key,
        typename Value,
        typename Constants,
        long Indexes,
        typename IndexKey,
        bool MapType
>
struct PackedMapFactory;

template <
        typename Key,
        typename Value,
        typename Constants,
        long Indexes,
        typename IndexKey
>
struct PackedMapFactory<Key, Value, Constants, Indexes, IndexKey, true> {
    typedef PackedValueMap<
        Key,
        Value,
        Constants,
        Indexes,
        IndexKey
    >                                                                           Type;
};


template <
        typename Key,
        typename Value,
        typename Constants,
        long Indexes,
        typename IndexKey
>
struct PackedMapFactory<Key, Value, Constants, Indexes, IndexKey, false> {
    typedef PackedIndexMap<
        Key,
        Value,
        Constants,
        Indexes,
        IndexKey
    >                                                                           Type;
};

} //tools
} //cubefs

#endif //_CUBEFS_CORE_TOOLS_PACKED_MAP_H
